package com.ww.springboot.boot.algorithm.leetcode1;

import java.util.ArrayList;
import java.util.List;

/**
 * todo
 *
 * @author wanwei
 * @since 2022-03-16 09:52
 */
public class AS77组合2 {

    public static void main(String[] args) {
        int n = 10, k = 6;
        System.out.println(combine(n, k));
    }

    public static List<List<Integer>> combine(int n, int k) {
        if (k > n) {
            return new ArrayList<>();
        }
        List<String> listAll = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            combine2(n, k - 1, "" + i, i, listAll);
        }
        List<List<Integer>> list = new ArrayList<>();
        for (int i = 0; i < listAll.size(); i++) {
            String[] chars = listAll.get(i).split(",");
            List<Integer> listSon = new ArrayList<>();
            for (int j = 0; j < chars.length; j++) {
                listSon.add(Integer.valueOf(chars[j]));
            }
            list.add(listSon);
        }
        return list;
    }

    public static void combine2(int n, int k, String origin, int max, List<String> listAll) {
        //2.剪枝 如果剩下的可选数据 + origin长度小于 k 则不需要再遍历下去了
        if((n -max) + origin.length() <k){
            return;
        }

        if (k == 0) {
            listAll.add(origin);
            return;
        }
        for (int i = 1; i <= n; i++) {
            //1.去掉重复数据
            if (i <= max) {
                continue;
            }

            combine2(n, k - 1, origin + "," + i, i, listAll);
        }
    }
}
